package twobranchsearch.Treebfsiterator;

import java.util.Stack;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/10
 * @author 王光浩
 * @Thinking 使用迭代+中序方式进行，
 * @Analysis 总体时间复杂度O（n），平均摊到每一个next上则是O（1），空间复杂度O（height）
 * @More 该方法还有一点比方法1好，在方法一中，当我们初始化迭代器时必须花费O（n）时间复杂度来中序遍历二叉搜索树，
 * 		 但是我们使用该方法则不然，只有当我们调用next方法时，才会进行中序遍历，是一个受控制的中序遍历。
 */
public class MyMethodTwo {
	Stack<TreeNode> stack;
	TreeNode next;
	public MyMethodTwo(TreeNode root) {
		stack=new Stack<TreeNode>();
		next=root;
	}
	    
	/** @return the next smallest number */
	public int next() {
		while(next!=null) {
			stack.push(next);
			next=next.left;
		}
		next=stack.pop();
		int res=next.val;
		next=next.right;
		return res;
    }
	    
	/** @return whether we have a next smallest number */
	public boolean hasNext() {
		return !stack.isEmpty() || next!=null;
	}
}
